/**
 * Created with IntelliJ IDEA.
 * Description:链式队列
 * User: LianBao
 * Date: 2024-04-04
 * Time: 12:59
 */
public class MyQueue<E> {

    //使用双向链表
    static class ListNode {
        public ListNode next;//前驱
        public ListNode prev;//后继
        public Object val;//值

        //构造方法用于初始化
        public ListNode(Object val) {
            this.val = val;
        }
    }

    public ListNode head;//头
    public ListNode tail;//尾

    //入队->只能从尾部入队(尾插)
    public void offer(E val) {
        ListNode newNode = new ListNode(val);
        //第一次入队
        if (tail == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    //出队->只能从头部出队(头删)
    public E poll() {
        if (empty()) {
            return null;
        }
        Object ret = head.val;

        head = head.next;
        head.prev = null;
        return (E) ret;
    }

    //获取队头元素
    public E peek() {
        if (empty()) {
            return null;
        }
        return (E)head.val;
    }

    //判断队列是否为空
    public boolean empty() {
        return head == null;
    }

}